/*
 * @lc app=leetcode.cn id=241 lang=cpp
 *
 * [241] 为运算表达式设计优先级
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:

    size_t find_first_op(const string& s, size_t pos)
    {
        for(size_t i = pos; i < s.size(); i++)
        {
            if(s[i] == '+' || s[i] == '-' || s[i] == '*')
                return i;
        }
        return s.npos;
    }

    int cal(char op, int l, int r)
    {
        switch (op)
        {
        case '-':
            return l - r;
        case '+':
            return l + r;
        case '*':
            return l * r;        
        default:
            break;
        }
        return 0;
    }

    vector<int> divide_conquer(string s)
    {
        size_t pos = find_first_op(s, 0);
        if(pos == s.npos)
        {
            return {stoi(s)};
        }

        vector<int> ans;
        while(pos != s.npos)
        {
            auto ls = divide_conquer(s.substr(0, pos));
            auto rs = divide_conquer(s.substr(pos + 1, s.size() - pos - 1));
            for(auto l : ls)
            {
                for(auto r : rs)
                {
                    ans.push_back(cal(s[pos], l, r));
                }
            }
            pos = find_first_op(s, pos + 1);
        }
        return ans;
    }

    vector<int> diffWaysToCompute(string expression)
    {
        return divide_conquer(expression);
    }
};


// int main()
// {
//     Solution().diffWaysToCompute("2-1-1");
//     return 0;
// }
// @lc code=end
